The present invention relates to the circuit having encoder and decoder of error correction codes.
Many error correction codes (ECC) currently used consist of linear codes or systematic codes. Systematic code is a category of code where data to be sent has a form of xe2x80x9coriginal data +parity,xe2x80x9d which is used in many application ECCs. These codes for ECC applications also incorporate Galois field or Galois extension fields which are a kind of number system used in the code.
For purposes of explanation of this invention it should be understood that word symbol length n (a symbol is data of 1 bit or multiple bits put together in a lump, and used as a synonym of byte or word), information word (message word or data word) symbol length k, generator matrix G (a matrix for calculating a parity by matrix operation on encoder) of linear code (n, k) on Galois extension field GF (2m) of m-bit symbol length or Galois field GF (2), and parity check matrix H (a matrix for calculating a syndrome on decoder), where G is a kxc3x97n matrix, and H is a (nxe2x88x92k)xc3x97n matrix. The syndrome information shows what and where an error has occurred in the data that must be calculated in a decoder.
An encoding calculation is performed for acquiring vG for the information word v (km bit) of symbol length k, and syndrome calculation in decoding is performed for acquiring wHT for received word w (nm bit) of symbol length n (where HT is a matrix of H). The above two calculations are both linear operations performed on GF (2m) or GF (2), and normally rendered a circuit by combining XOR gates in the form of XOR calculation. Each row vector of G and each row vector of H are linearly independent on GF (2m) or GF (2) respectively.
Systematic code includes the original information word in symbol k portion and also includes a parity word in the remaining symbol nxe2x88x92k portion.
In linear code and systematic code, of generator matrix of kxc3x97n matrix, the kxc3x97k area forms a unit matrix to embed an information word in the code word so that the process substantially performed in the encoder is applied only to an information word kxc3x97(nxe2x88x92k) matrix, of the generator matrix of kxc3x97n matrix, which generates a parity word. In the following description this kxc3x97(nxe2x88x92k) matrix will be referred to as G.
Depending on what circuit encodes and what syndrome calculation are to be performed, will determine whether the information word or received word is serial or parallel mode. If it is serial, it is implemented in a sequential circuit by using LFSR (Linear Feedback Shift Register, a kind of a shift register), etc. If the entire information word is in parallel mode, the word is encoded or decoded in parallel (hereafter, xe2x80x9cparallel encoding/decodingxe2x80x9d), it is implemented in a combinational circuit.
In the case where a decoder is implemented not in parallel encoding/decoding but in a sequential circuit (syndrome calculation and Chien search, for instance, are similar in circuit configuration) a method of sharing a register may be used. These are described in xe2x80x9cCircuit for Generating Polynomials for Error Correction Calculationxe2x80x9d (Japanese Unexamined Patent Publication No. Hei 3-190326), xe2x80x9cReed-Solomon Circuit for Decoding Error Correction Codexe2x80x9d (Japanese Unexamined Patent Publication No. Hei 8-139612), and the following document: xe2x80x9cAn Area-Efficient VLSI Architecture of a Reed-Solomon Decoder/Encoder for Digital VCRs,xe2x80x9d S. Kwon and H. Shin, IEEE trans. on Consumer Electronics, Vol.43, No.4, pp.1019-1027, November , 1997, etc.
In a combinational circuit, coordination of common portions (so called xe2x80x9cResource Sharingxe2x80x9d) among multioutput logic functions includes a circuit design which performs the same calculation as separate circuits of the same system that are put together to act like a single circuit.
The method for using a decoder as an encoder for Reed-Solomon code is described in , xe2x80x9cUse of the RS Decoder as an RS Encoder for Two Way Digital Communications and Storage Systems,xe2x80x9d C. C. Hsu, I. S. Reed, and T. K. Truong, IEEE Transactions on Circuits and Systems for Video Technology, Vol.4, No.1, pp.91-92, February, 1994.
According to this article, it is a prerequisite to use a decoder with an erasure decoding feature, and indicates that it is difficult in a code such as Reed-Solomon code to correct erasure with parallel code. The problem in such a method is that encoding takes as long a time as decoding.
Parallel encoding/decoding is performed in the case where high speed is required and data is in parallel mode.
For example, in a memory system where:
(i) Error correction circuit of high speed and low power consumption for extending DRAM refresh time (QNVRAM)
where coordination of a group of encoders will be effective. Codes of different error correction capability should be concurrently used in order to improve flexibility and reliability of the system. (For example, see the specification of Japanese Unexamined Patent Publication No. Hei 10-13586.)
(ii) Error correction circuit for computer main storage that requires reliability (Memory ECC), where ECC is applied to memory in parallel encoding/decoding. In which case, the encoding should be performed at a high speed while error correction is slow.
(iii) Error correction code is used in a multiple manner in order to improve error correction capability, and if a high-speed decoding process is required in spite of originally slow data transfer speed.
For instance, in a future high-speed communication, etc. where there may arise the necessity to decrease packet retransmission by using a powerful ECC or to dynamically change error correction capability according to the situation, then effective coordination of a group of encoders is necessary.
Implementation of such parallel encoding/decoding circuit is equal to implementing a combinational circuit by deploying a sequential circuit, which generally makes circuit size much larger even though it depends on input word length and error correction capability. Thus, such parallel encoding/decoding could be performed only to code of low error correction capability. However, as implementable circuit size has increased in recent years, code allowing parallel encoding/decoding has also increased, heightening the importance of holding down the circuit size.
Also, each encoder must be made separately because the circuits of different error correction capability create the problem of a circuit becoming too large.
In addition, if information word length (data length) increases, it causes the corresponding problem of circuit size increasing.
An objective of the present invention is to improve a system having multiple encoders with varying maximum error correction capability, while reducing the size of the circuit by allowing most of the system to be shared among these encoders.
Another objective is to reduce the size of the system (combining encoders and decoders) by integrating circuits for parallel encoding/decoding and allowing sharing of most of the encoders and most of the syndrome generator in the decoders.
Further objective is to reduce the size of the circuit by holding down the extent of increase of the scale of the circuit even if information word length, (ie data length) has increased.
To attain these objectives, the present invention offers the following circuit.
An encoder capable of calculating parities of xcex1 (where, xcex1 is an integer of 2 or more) kinds of bit numbers with different error correction capability, comprising: a first circuit for generating a modified word by assigning a predetermined value to the input information word; a first circuit connected to the first circuit for generating intermediate signal xe2x80x9cuxe2x80x9d by linear operation using the modified word and matrix xe2x80x9cPxe2x80x9d; and a second circuit connected to the first circuit all or part of the intermediate signal and matrixes Q1, . . . , Qxcex1 respectively.
A circuit having a single encoder and decoder capable of calculating parities of xcex1 (here, xcex1 is an integer of 1 or more) kinds of bit numbers with different error correction capability. The circuit comprising: a first circuit that generates a modified word by assigning a predetermined value if the input message is an information word without any parity; a second circuit is connected to the first circuit that generates an intermediate signal by linear operation using the modified word and matrix P; a third circuit connected to the second circuit that generates a syndrome value of s1, . . . , sxcex1, by linear operation using all or part of the intermediate signal and matrixes R1, . . . , Rxcex1 respectively; and a fourth circuit connected to the second circuit having an xcex1 linear operation that generates a value of parity p1, . . . , pxcex1, each of whose bit number is different, by linear operation using all or part of the intermediate signal and matrixes Q1, . . . , Qxcex1.
A circuit having a single encoder and decoder capable of calculating parities of xcex1 (here, xcex1 is an integer of 1 or more) kinds of bit numbers with different error correction capability. The circuit comprising: a first circuit that generates a modified word by assigning a predetermined value if the input message is an information word without any parity; a second circuit connected to the first circuit that generates an intermediate signal by linear operation using the modified word and matrix P; a third circuit connected to the second circuit that generates a all or part of the intermediate signal and matrixes R; and a fourth circuit connected to the second circuit having an xcex1 linear operation that generates a value of parity p1, . . . , pxcex1, each of whose bit number is different, by linear operation using all or part of the intermediate signal and matrixes Q1, . . . , Qxcex1.
A circuit having a single encoder and decoder capable of calculating parities of xcex1 (here, xcex1 is an integer of 1 or more) kinds of bit numbers with different error correction capability. The circuit comprising: a first circuit that generates a modified word by assigning predetermined value if input message is information word without any parity; a second circuit connected to the first circuit that generates an intermediate signal by linear operation using the modified word and matrix P, the intermediate signal being syndrome value of s1, . . . , sxcex1 if the input message is received word; and a second circuit connected to the first linear operation circuit having xcex1 linear operation circuits for generating value of parity p1, . . . , pxcex1, each of whose bit number is different, by linear operation using all or part of the intermediate signal and matrixes Q1, . . . , Qxcex1 respectively.